#include "LinkList.h"
#include<iostream>

LinkList::LinkList():size(0)
{
   // 头结点：为了编程方便而存在的结点，不放置有效数据
    head = new Node(0);
}



LinkList::~LinkList()
{
    while(head != nullptr)
    {
        Node* nextNode = head ->next;//记下下一个结点
        delete head;
        head = nextNode;// 结点往后走
    }
}




void LinkList::InsertTail(const ElementType &element)
{
    // 遍历指针
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = new Node(element); //()小括号在这里是初始化的作用，相当于调用构造函数
    size++; 
}

void LinkList::InsertHead(const ElementType &element)
{
    Node* newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void LinkList::InsertByIndex(int index,const ElementType &element)
{
    // 从头节点开始数index个,最终停在index-1个结点上
    Node* travelPoint = head;
    
    for(int i=0;i<index;i++)
    {
        travelPoint = travelPoint->next;
    }
    Node* newNode = new Node(element);
    
    newNode->next = travelPoint->next;
    
    travelPoint->next = newNode;
    size++;
}

void LinkList::RemoveByIndex(int index)
{
    if(index<0 || index >= size)
    {
        std::cout<<"非法的删除位置\n";
        return;
    }
    Node* travelPoint = head;
    for(int i=0;i<index;i++)
    {
        travelPoint = travelPoint->next;
    }
    Node* freeNode = travelPoint->next;

    travelPoint->next = freeNode->next;

    delete freeNode;
    size--;
}


void LinkList::RemoveByElement(const ElementType &element) // O(n)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {
            Node* freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--; 
        }
        else
        travelPoint = travelPoint->next;
    }
}

 LinkList::ElementType *LinkList::FindByIndex(int index)
{
    if(index <0 || index >= size)
    {
        std::cout<<"非法的位置\n";
        return nullptr;
    }
    
    Node* travelPoint = head;
    for(int i=0;i <= index;i++)
    {
        travelPoint = travelPoint->next;
    }

    return &travelPoint->data;

}

DynamicArray LinkList::FindByElement(const ElementType &element)
{
    Node *travelPoint = head;
    
    DynamicArray result;
    
    while (travelPoint->next != nullptr)
    {
        if(travelPoint->data == element)
        {
            result.InsertTail(&travelPoint->data);
        }
        travelPoint = travelPoint->next;
    }
    return result;     
}

void LinkList::BubbleSort()
{
    for(int i=0;i<size-1;i++)
    {
        Node* travelPoint = head;  //每一次都从头开始扫描 链表
        
        for(int j=0;j<size-i-1;j++)
        {
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *prevNode = travelPoint->next;//来比较的 两个结点中的 前一个
                Node *backNode = prevNode->next;    //来比较的 两个结点中的 后一个

                prevNode->next = backNode->next;
                backNode->next = prevNode;

                travelPoint->next = backNode;
            }
            travelPoint = travelPoint->next;
        }
    }
}


// 双指针:快慢指针

void LinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;
    Node *temp = start; //基准值指针
    Node *slow = start; //慢指针
    Node *fast = slow->next; //快指针 

    while(fast != end) //不走到末尾
    {
        if(fast->data <temp->data)
        {
        slow = slow->next;
        std::swap(slow->data,fast->data); //交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(slow->data,temp->data);//基准值归为
    //递归
    FastSort(start, slow);
    FastSort(slow->next,end);

}






void LinkList::Sort()
{
    FastSort(head->next,nullptr);
}
// 逆序
void LinkList::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head->next;
    Node *back = cur->next;

    while(back != nullptr)
    {
        cur->next = prev; //逆序
        prev = cur;
        cur = back;
        back = cur->next;

    }
    cur->next = prev;//最后一个结点单独逆序
    head->next = cur;//新的链表头给到  head 的 next
}




void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

LinkList::Node *LinkList::Reserve2(Node *node)
{
    if(node->next == nullptr)
    {
        return node;//返回原来的尾巴，逆序之后的链表的头
    }
    
    else
    {
        Node*newHead = Reserve2(node->next);
        
        node->next->next = node; //逆序
        node->next = nullptr; // 新的最后一个结点指向空
        
        return newHead; //把新的头层层返回
    }
}


void LinkList::show()
{
    Node *travelPoint = head->next;
    std::cout<<"size:"<<this->size<<std::endl;
    while (travelPoint != nullptr)
    {   
        std::cout<<travelPoint->data<<" ";
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
}
